(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
                              ОТДЕЛ ОбменомБ;
(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
(* НАЗНАЧЕНИЕ: упорядочивание ряда быстрым обменом ("быстрая сортировка")     *)
(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)

(*────────────────────────────────────────────────────────────────────────────*)
ЗАДАЧА Упорядочить-(ряд+:РЯД ИЗ ЦЕЛ);
(* Цель:  упорядочивание с помощью разделения на участки (Ч.Хоар)
 * До:    <ряд> - исходный ряд
 * После: <ряд> - упорядоченный ряд *)
ПЕР
  Л,П:ЦЕЛ;     (* текущий участок                   *)
  л,п:ЦЕЛ;     (* новый участок                     *)
  граница:ЦЕЛ; (* граничное значение для разделения *)
  рядл:ЦЕЛ;    (* промежуточное значение для обмена *)
  глубина:ЦЕЛ; (* текущая глубина стека             *)
  стек:РЯД 32 ИЗ НАБОР Л,П:ЦЕЛ КОН; (* стек для новых участков *)
УКАЗ
  глубина:=0; 
  стек[0].Л:=0; 
  стек[0].П:=РАЗМЕР(ряд)-1;
  ПОВТОРЯТЬ
    (* выбор из стека последнего запроса *)
    Л:=стек[глубина].Л; 
    П:=стек[глубина].П;
    УМЕНЬШИТЬ(глубина);
    ПОВТОРЯТЬ
      (* разделение ряд[Л]...ряд[П] *)
      л:=Л; п:=П;
      граница:=ряд[(Л+П) ДЕЛИТЬ 2];
      ПОВТОРЯТЬ
        ПОКА ряд[л] > граница ВЫП УВЕЛИЧИТЬ(л) КОН;
        ПОКА граница > ряд[п] ВЫП УМЕНЬШИТЬ(п) КОН;
        ЕСЛИ л <= п ТО (* обмен местами ряд[л] с ряд[п] *)
          рядл:=ряд[л];
          ряд[л]:=ряд[п];
          ряд[п]:=рядл;
          УВЕЛИЧИТЬ(л);
          УМЕНЬШИТЬ(п)
        КОН
      ДО л > п;
      ЕСЛИ п-Л < П-л ТО
        ЕСЛИ л < П ТО (* запись в стек запроса на упорядочивание правой части *)
          УВЕЛИЧИТЬ(глубина);
          стек[глубина].Л:=л;
          стек[глубина].П:=П
        КОН;
        П:=п (* продолжение упорядочивания левой части *)
      ИНАЧЕ
        ЕСЛИ Л < п ТО (* запись в стек запроса на упорядочивание левой части *)
          УВЕЛИЧИТЬ(глубина);
          стек[глубина].Л:=Л;
          стек[глубина].П:=п
        КОН;
        Л:=л (* продолжение упорядочивания правой части *)
      КОН
    ДО Л >= П
  ДО глубина < 0
КОН Упорядочить;

КОН ОбменомБ.

▲ Вопросы, замечания и предложения высылайте на atimopheyev@yahoo.com или Издателю Глагола: